PSI系列（3）组件 | OT Extension (KK13)

前置知识可阅读下方推文：PSI系列（1）组件 | Cuckoo HashingPSI系列（2）组件 | OT Extension (IKNP)

1

编码知识

[定义] 有限域上维向量空间的每个非空子集都叫做一个元纠错码[1]。叫做元线性码是指：若，则。码字：指中的某个具体的向量。码长：码字的长度。码字个数：。信息位数：不考虑纠错问题，个信息用元域中的元素来表示每位，只需要位即可，因此有。信息位数可以理解为想要发送的真实数据的长度，而码长可以理解为实际传输过程中所用的数据长度。传输效率：。汉明重量：向量中非零分量的个数。汉明距离：向量和之间的汉明距离指的是向量的汉明重量，即和有多少个对应分量是不同的。最小距离：中任意两个不同码字的汉明距离的最小值。其中码长，信息位数和最小距离是三个重要参数，元纠错码也可以表示为。[例子] 奇偶校验码将中的16个信息编成中的子集合，得到

。因此这个线性纠错码可以表示为。

2

KK13IKNP协议[2]高效地实现了次1-out-of-2 OT实例，KK13协议[3]则希望实现次1-out-of- OT实例。回顾一下，IKNP协议中生成的那两个矩阵和，对于第行来说，如果以编码的角度，可以理解为的结果是一个码长为，信息位数为1的重复编码，其中，。将编码的码字个数扩大，是否能实现1-out-of- OT 实例呢？接下来看一下KK13协议的过程：发送方的输入：，其中，。接收方的输入：由个选择比特构成的向量，，。公共输入：安全参数及Walsh-Hadamard codes （可视为一种线性纠错码，论文中写它的码长和码字个数均为，当为2的幂时最小距离为）。
1. 随机选取向量，随机生成大小为的01矩阵和，使得对于，满足。 2. 两方调用，其中作为发送方提供输入，作为接收方提供输入。 3. 将次OT得到的结果合并成一个的矩阵。按照上一篇文章中的推导，很容易得到（表示逐比特AND操作）。4. 对于和，发送给。 5. 对于，计算。
经过对比可以发现，KK13协议相比于IKNP协议最明显的改动在于生成矩阵和的方式，两个矩阵对应行的异或结果由全0或全1变成了空间更大的编码，这使得密钥从和拓展为，也只能解密对应的密文。如果想要获得另一个字符串对应的密钥，根据
可知，对于来说唯一的未知量是，由Walsh-Hadamard codes的最小距离为可知至少有位不为0，那么需要猜中在这位的值，才能破坏协议的安全性。对于KK13协议，要求其安全参数。
3
利用构造 上一篇文章介绍了在的情况下，如何使用次base OT来生成次OT实例，以达到显著降低开销的目的。本节是对上文的补充，为后续效率分析做铺垫。发送方输入：，其中。接收方输入：由个选择比特构成的向量。接收方输出：。构造过程：1. 生成对随机的种子，其中。 2. 两方调用，作为发送方提供输入，作为接收方提供输入。 3. 对于，发送，其中，为伪随机生成器。 4. 对于，输出。整个构造过程非常直观，利用伪随机生成器来实现消息长度的拓展，由于与相距过大，因此产生的开销可以被视为常数，大部分开销来源于第三步中发送给的个字符串。
4

效率分析IKNP协议的通信开销来源于和次1-out-of-2 OT实例中传输的加密消息对，前者为比特，后者为比特，因此总通信开销为比特。KK13协议的通信开销来源于和次1-out-of- OT实例中传输的加密消息对，前者为比特，后者为比特，因此总通信开销为比特。关于计算开销，主要来源于和对的计算，论文中写两个协议的总计算开销均与通信开销成正比。
5

参考文献

[1]:冯克勤. 代数与通信[M]. 高等教育出版社, 2005.

[2]:Ishai Y, Kilian J, Nissim K, et al. Extending Oblivious Transfers Efficiently[C]//Crypto. 2003, 2729: 145-161.

[3]:Kolesnikov V, Kumaresan R. Improved OT extension for transferring short secrets[C]//Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II. Springer Berlin Heidelberg, 2013: 54-70.

本文来源：https://zhuanlan.zhihu.com/p/620120440

作者简介：林中允，华东师范大学软件工程学院密码与网络安全系研究生，主要研究方向为多方隐私集合求交。知乎：@云波随风尽

END

往期推荐

1.CCVR：一种生成虚拟数据的联邦学习算法
2.密码学的100个基本概念（上）3.密码学的100个基本概念（下）4.笔记分享 | 组队学习密码学（1）——密码学与MPC基础